def quick_sort_default(array):
    quick_sort(array, 0, len(array)-1)
    return array


def quick_sort(array, lo, hi):
    if hi - 2 < lo:
        return
    m = partition(array, lo, hi)
    quick_sort(array, lo, m)
    quick_sort(array, m+1, hi)


def partition(array, lo, hi):
    import random
    backup = array[lo]
    pivot_index = random.randint(lo, hi)
    pivot = array[pivot_index]
    swap(array, pivot_index, lo)
    while lo < hi:
        while lo < hi and array[hi] >= pivot:
            hi -= 1
        array[lo] = array[hi]
        while lo < hi and array[lo] <= pivot:
            lo += 1
        array[hi] = array[lo]
    array[lo] = pivot
    return lo


def swap(array, index1, index2):
    temp = array[index1]
    array[index1] = array[index2]
    array[index2] = temp


print(quick_sort_default([1, 1, 4, 8, 2]))
